package leetcode.new_wrold;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class T120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] pathSum = new int[n];
        pathSum[0] = triangle.get(0).get(0);
        int minSum = pathSum[0];

        List<Integer> list;
        for (int i = 1;i<n;i++){
            list = triangle.get(i);
            pathSum[i] = pathSum[i-1]+list.get(i);
            minSum = pathSum[i];
            for (int j=i-1;j>0;j--) {
                 pathSum[j] = Math.min(pathSum[j-1],pathSum[j])+list.get(j);
                 if (pathSum[j]<minSum){
                     minSum = pathSum[j];
                 }
            }
            pathSum[0] = pathSum[0]+list.get(0);
            if (pathSum[0]<minSum){
                minSum = pathSum[0];
            }
        }
        return minSum;
    }

    public static void main(String[] args) {
        T120 t120 = new T120();
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        list1.add(-10);
//        List<Integer> list2 = new ArrayList<>();
//        list2.add(3);        list2.add(4);
//        List<Integer> list3 = new ArrayList<>();
//        list3.add(6);        list3.add(5);     list3.add(7);
//        List<Integer> list4 = new ArrayList<>();
//        list4.add(4);        list4.add(1);     list4.add(8);   list4.add(3);

        list.add(list1);
//        list.add(list2);
//        list.add(list3);
//        list.add(list4);
        int minimumTotal = t120.minimumTotal(list);
        System.out.println(minimumTotal);
    }
}
